#include <stdio.h>
#include <string.h>
unsigned long long P = 233; 
unsigned long long MOD = 1e9+7;
unsigned long long p[1000010];
char str1[1000010];
char str2[1000010];
unsigned long long hash1[1000010];
unsigned long long hash2[1000010];
int len1,len2;
void gethash()
{
	hash1[0] = str1[0]-'A';
	hash2[0] = str2[0]-'A';
	for(int i=1;i<len1;i++)
	{
		hash1[i] = (hash1[i-1]*P+str1[i]-'A');
	}
	for(int i=1;i<len2;i++)
	{
		hash2[i] = (hash2[i-1]*P+str2[i]-'A');
	}
}
int main()
{
	long long int t,flag,ans;
	p[0]=1;
	for(int i = 1;i<1000010;i++)
	{
		p[i] = p[i-1]*P;
	}
	scanf("%d",&t);
	while(t--)
	{
		ans = 0;
		scanf("%s",str1);
		scanf("%s",str2);
		len1 = strlen(str1);
		len2 = strlen(str2);
		gethash();
		for(int i = 0;i<=len2-len1;i++)
		{
			flag = 0;
			if(i==0)
			{
				if(hash1[len1-1]==hash2[len1-1])
				{
					ans++;
					flag=1;
				}
			}
			else
			{
				int r = i+len1-1;
				int l = i-1;
				long long temp;
				temp = hash2[r]-(hash2[l]*p[len1]);
				//printf("*****%d %d\n",temp,hash1[len1-1]);
				if(temp==hash1[len1-1])
				{
					ans++;
					flag=1;
				}
			}
		}
		printf("%I64d\n",ans);
	}
} 
